public class TreeMap implements Map {

	private BinarySearchTree bst;
	private int size;


	private static class Entry implements Comparable {
		Comparable key;
		Object value;

		Entry( Comparable k ) {
			key = k;
			value = null;
		}

		Entry( Comparable k, Object v ) {
			key = k;
			value = v;
		}

		public boolean equals( Object obj ) {
			if ( obj instanceof Entry ) {
				return compareTo( obj ) == 0;	
			}
			else {
				return false;
			}
		}

		public int compareTo( Object obj ) {
			Entry other = (Entry)obj;
			return key.compareTo( other.key );
		}
	}


	public TreeMap() {
		init();
	}


	private void init() {
		bst = new BinarySearchTree();
		size = 0;
	}
	

    public int size( ) {
		return size;
	}
    

    public boolean isEmpty( ) {
		return size == 0;
	}


    public Object put( Object key, Object value ) {
		Entry newEntry = new Entry( (Comparable)key, value );
		Entry entry = (Entry)bst.find( newEntry );
		if ( entry != null ) {
			Object tmp = entry.value;
			entry.value = value;
			return tmp;
		}
		else {
			bst.insert( newEntry );
			return null;
		}
	}


    public boolean containsKey( Object key ) {
		Entry tmpEntry = new Entry( (Comparable)key );
		return bst.find( tmpEntry ) != null;
	}


    public Object get( Object key ) {
		Entry tmpEntry = new Entry( (Comparable)key );
		Entry entry = (Entry)bst.find( tmpEntry );
		if ( entry != null ) {
			return entry.value;
		}
		else {
			return null;
		}
	}


    public Object remove( Object key ) {
		Entry tmpEntry = new Entry( (Comparable)key );
		Entry entry = (Entry)bst.find( tmpEntry );
		if ( entry != null ) {
			Object tmp = entry.value;
			bst.remove( entry );
			return tmp;
		}
		else {
			return null;
		}
	}


    public void clear( ) {
		init();
	}

}